package com.zx._12_算法.数据结构.tree;

import com.zx._12_算法.TreeNode;
import org.junit.Test;

/*
    给你一串字符，像 4(2(3)(1))(6(5))，把它变成一棵真正能遍历的二叉树。
    面试高频、线上也常用（比如配置里写一棵规则树）。
    字符串长啥样本文用括号表达式这种常见格式：val(left)(right)，左右子树可省略。
    示例：
    1 → 只有根节点
    1(2) → 左子树是 2，右子树为空
    4(2(3)(1))(6(5)) → 完整左右子树

    注意：节点值可为负数、多位数；空子树允许缺省（比如只有一个 (left)）。
    
    思路别慌，就三步（递归）
    1. 顺序扫描字符串，用一个游标 index走到底。
    2. 读出一个整数作为当前节点值。
    3. 如果后面遇到 '('，递归解析一棵子树；遇到 ')' 就返回到上一层。
    这个结构天然是先序：根 → 左 → 右；括号帮你界定子树边界，不需要额外栈。
 */
public class A1_从字符串生成二叉树 {

    private int idx = 0;

    @Test
    public void run() {
        TreeNode root = run("4(2(3)(1))(6(5))");
        root.print();
        /*
            4(2(3, 1), 6(5, ))
            4(2(3(, ), 1(, )), 6(5(, ), ))
         */
    }

    public TreeNode run(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        char r = str.charAt(idx);
        idx++;
        TreeNode root = new TreeNode(Integer.parseInt(String.valueOf(r)));

        boolean left = true;
        while (idx < str.length()) {
            char ci = str.charAt(idx);
            idx++;
            TreeNode node = null;
            if ('(' == ci) {
                node = run(str);
            } else if (')' == ci) {
                return root;
            } else {
                node = new TreeNode(Integer.parseInt(String.valueOf(ci)));
            }

            if (left) {
                root.left = node;
                left = false;
            } else {
                root.right = node;
            }
        }

        return root;
    }

}
